/*
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

class Solution {
public:
	vector<int> vis;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
		vector<vector<int>> ans;
        vector<int> combine;
        vis.resize(nums.size());
        sort(nums.begin(), nums.end());
        backtrack(nums, combine, ans, 0, nums.size());
        return ans;
    }
	
	void backtrack(vector<int>& nums, vector<int> combine, vector<vector<int>>& ans, int index, int len) {
        if (index == len) {
            ans.emplace_back(combine);
            return;
        }
        for (int i = 0; i < (int)nums.size(); ++i) {
            if (vis[nums[i]] && index > 0) {
                continue;
            }
			if(index == 0){
				vis.emplace_back(nums[i]);
			}
			index++;
			
            combine.emplace_back(nums[i]);
            backtrack(nums, combine, ans, index + 1, len);
            combine.pop_back();
			index--;
        }
    }
};

int main(){
	vector<int> a = {1,2,1,2};
	Solution so;
	auto res = so.permuteUnique(a);
	
	for(auto items : res){
		for(auto item : items){
			cout << item << ",";
		}
		cout << endl;
	}
	return 0;
}